package com.kehao.leetcode.middle.linked_list;

import org.junit.Test;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}


public class OddEvenListSolution {
    public ListNode oddEvenList(ListNode head) {
        if(head==null||head.next==null) return head;
        ListNode p = head,p_next = p.next;
        ListNode oddHead = new ListNode(),pOdd = oddHead;//此处头节点不带数据
        ListNode evenHead = new ListNode(),pEven = evenHead;//此处头节点不带数据
        for (int i = 1; p!=null; i++) {
            if(i%2==1){
                p.next = pOdd.next;
                pOdd.next = p;
                pOdd = p;
            }else {
                p.next = pEven.next;
                pEven.next = p;
                pEven = p;
            }
            p = p_next;
            if(p!=null){
                p_next = p.next;
            }
        }
        oddHead=oddHead.next;
        pOdd.next = evenHead.next;
        return oddHead;

    }

    @Test
    public void test01(){
        int[] nums = {1,2,3,4,5};
        ListNode node =new ListNode(0);
        ListNode head = node;
        for(int num:nums){
            node.next = new ListNode(num);
            node=node.next;
        }
        head = head.next;
        head = oddEvenList(head);
        while (head!=null){
            System.out.print(head.val+" ");
            head=head.next;
        }
    }
}
